#include<stdio.h>
#include<math.h>
double Lagrange(float a,double x[],double y[],int n)
{

    double f,L=0;
    int i,j;

    for (i=0;i<n;i++)
    { 
        f=1; 
        for (j=0;j<n;j++)  
            if(j!=i) 
            	f=(a-x[j])/(x[i]-x[j])*f; 
        L+=f*y[i]; 
    }
    return L;     
}
double ND(float a,double x[],double y[],int n)
{

    double p=0,g,f;
    int i,j,k;

    for (i=0;i<n-1;i++)
    { 
            for (j=n-1;j>i;j--)
            {
				f=x[j]-x[j-i-1];y[j]=(y[j]-y[j-1])/f;
			}
            g=y[i+1];
            for (k=0;k<=i;k++) 
                g=g*(a-x[k]); 
            p=p+g;
    }
    return p+y[0];     
}

double hermiteInterpolation(double target)
{
	double x[3]={1.0,2.0,3.0},y[3]={0.367879441,0.135335283,0.049787068},dy[3]={-0.367879441,-0.135335283,-0.049787068};
    double t = (target - x[0]) / (x[1] - x[0]);
    double t2 = t * t;
    double t3 = t2 * t;

    double a0 = y[0];
    double a1 = dy[0];
    double a2 = (3.0 * (y[1] - y[0]) / pow((x[1] - x[0]), 2)) - ((2.0 * dy[0]) / (x[1] - x[0])) - ((dy[1]) / (x[1] - x[0]));
    double a3 = (2.0 * (y[0] - y[1]) / pow((x[1] - x[0]), 3)) + ((dy[0] + dy[1]) / pow((x[1] - x[0]), 2));

    double interpolatedValue = a0 + (a1 * t) + (a2 * t2) + (a3 * t3);

    return interpolatedValue;
}

int main()
{
	double a=2.6,x[3]={1.0,2.0,3.0};
	static double y[3]={0.367879441,0.135335283,0.049787068},dy[3]={-0.367879441,-0.135335283,-0.049787068};
	double result = Lagrange(a,x,y,3);
	printf("拉格朗日插值法:%.9lf\n",result);
	result = ND(a,x,y,3);
	printf("牛顿插值法:%.9lf\n",result);
	double result2 = hermiteInterpolation(a);
	printf("hermter插值法:%.9lf\n",result2);
	return 0;
}